package com.hspedu.newData.dmsxl.树.二叉树路径.路径;

import com.hspedu.newData.dmsxl.ds.TreeNode;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-26 
 * @Version: 1.0
 */

//todo
public class LC124二叉树中的最大路径和 {

    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    public int dfs(TreeNode root){
        if (root==null){
            return 0;
        }

        int leftMax = Math.max(dfs(root.left),0);
        int rightMax = Math.max(dfs(root.right),0);

        int priceNewPath = root.val + leftMax + rightMax;

        maxSum = Math.max(maxSum,priceNewPath);

        return root.val+Math.max(leftMax,rightMax);
    }
}
